package DARP;

import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.LinkedList;

public class DARP2 {

	private ArrayList<Location> vetorDosPontos = new ArrayList<Location>();//Apenas para referenciar 
	//private ArrayList<int[]> solucao = new ArrayList<int[]>();
	private ArrayList<Rota> solucao = new ArrayList<Rota>();
	//private ArrayList<float[]> listaDeVariaveis = new ArrayList<float[]>();

	private Data data = Data.getPRVData();
	int //valorLimiteDosPontosDeEmbarque, 
	limiteDosEmbarques = data.getQuantidadeDePontosDeColetas()/2, 
	tempMaxCaronaCliente_R = data.getTempoMaxDeViagemCliente(),
	tempoMaxDaRotaVeiculo = data.getTempoMaxDeDuracaoDaRota(),
	cargaMaximaDoVeiculo = data.getCapacidadeDoVeiculo();
	private int[] id = data.getId(), veic = data.getVeiculos();//, acao = data.getAcao();
	private float[] coordX = data.getCoordX(), coordY = data.getCoordY();//, s = data.getTempoServico();
//	private float[][] matriz = data.getMatriz();
	private int[] capacidadeVeiculo = data.getCapacidadeDosVeiculos();
	//=========== FO ============
	private float funcaoObjetivo;
	private float w0, w1, w2, w3, w4, b0, b1, b2, b3, b4, velocidadeMedia = 20;
	//Data data;
	private float[] R_TempoMaximo_Rota;//, e = data.getInicioJanela(), l = data.getFimJanela();
	private float[][] matrizDistancia = data.getMatriz(), t = data.getT();
	private int qntVeiculos = data.getQuantidadeDeVeiculos(), qntPontos = data.getQuantidadeDePontosDeColetas(), W_TempoMaximo_Espera;
	private int[][][] x = new int[qntVeiculos][qntPontos][qntPontos];
	private int[] garagemInicial = data.getGaragensIniciais(), garagemFinal = data.getGaragensFinais();
	private boolean[] vetorVisitados = new  boolean[qntPontos];
	//	float[] A, B, D, R, W, T, Q, F;
	LinkedList<Integer>  elementosDaRota;
	int maxIter,  maxIterILS,  kpMax,  delta;

	//	LinkedList<Integer> rota,  A, B, D, W, R, T, Q, F, e, l, acao,  s;
	//	int tempoMaxDeViagemPermitidoCliente, int tempoMaxDaRotaVeiculo, int cargaMaximaDoVeiculo; 

	/**
	 * Constrói o vetor dos pontos para termos uma referência
	 */
	public void carregaDados(int tempoMaximoDeEsperaDoVeiculo_W){//Constrói o vetor com os dados para referencia
		float[] e_Location = data.getInicioJanela(), l_Location = data.getFimJanela(), s_Location = data.getTempoServico();
		int[] id_Location = data.getId(), acao_Location = data.getAcao();
		data.getPRVData();
		System.out.println("Leu os dados");
		for (int i = 0; i < qntPontos; i++) {
			System.out.println(i);
			Location location = new Location(coordX[i], coordY[i], e_Location[i], l_Location[i], s_Location[i],id_Location[i], acao_Location[i]);
			vetorDosPontos.add(location);

			vetorVisitados[i] = false;
			W_TempoMaximo_Espera = tempoMaximoDeEsperaDoVeiculo_W;
		}
		//valorLimiteDosPontosDeEmbarque = qntPontos/2;//TODO VERIFICAR LIMITES
		System.out.println("Os dados foram carregados com sucesso");
		System.out.println("Limite dos P: "+limiteDosEmbarques);
	}

	public void inicializaRotas(){//Cria as rotas vazias
		//int contVeiculos = 0;

		for (int k = 0; k < qntVeiculos; k++) { 
			LinkedList<Integer> rota = new LinkedList<Integer>(), acao = new LinkedList<Integer>();//int[2*capacidadeVeiculo[k]];//int[2*capacidadeVeiculo[contVeiculos]];//Vetor com os ids das requisicoes e das variaveis
			LinkedList<Float>  A = new LinkedList<Float>(), B = new LinkedList<Float>(), D = new LinkedList<Float>(), 
			W = new LinkedList<Float>(), R = new LinkedList<Float>(), T = new LinkedList<Float>(), Q = new LinkedList<Float>(),
			F = new LinkedList<Float>(), e = new LinkedList<Float>(), l = new LinkedList<Float>(),
			s = new LinkedList<Float>();
			//Adiciona a lista de variaveis as variaveis A B D R W T Q F
			//			float F[] = new float[2*capacidadeVeiculo[k]+2];
			//			float Q[] = new float[2*capacidadeVeiculo[k]+2];
			//			float T[] = new float[2*capacidadeVeiculo[k]+2];
			//			float W[] = new float[2*capacidadeVeiculo[k]+2];
			//			float R[] = new float[2*capacidadeVeiculo[k]+2];
			//			float D[] = new float[2*capacidadeVeiculo[k]+2];
			//			float B[] = new float[2*capacidadeVeiculo[k]+2];
			//			float A[] = new float[2*capacidadeVeiculo[k]+2];
			//			int[] acao = new int[2*capacidadeVeiculo[k]+2];
			//			float[] e = new float[2*capacidadeVeiculo[k]+2];
			//			float[] l = new float[2*capacidadeVeiculo[k]+2];
			//			float[] s = new float[2*capacidadeVeiculo[k]+2];
			float zero = 0;
			for (int i = 0; i < (2 + 2*capacidadeVeiculo[k]) ; i++) {
				rota.add(i, -1);
				System.out.println(i);
				A.add(zero);
				B.add(zero);
				D.add(zero);
				R.add(zero);
				W.add(zero);
				T.add(zero);
				Q.add(zero);
				F.add(zero);

				e.add(zero);
				l.add(zero);
				acao.add(0);
				s.add(zero);

			}
			rota.set(0, garagemInicial[k]);
			rota.set( (1 + 2*capacidadeVeiculo[k]) , garagemFinal[k]);

			Rota rotaVeiculo = new Rota(rota, A, B, D, W, R, T, Q, F, e, l, acao, s, tempMaxCaronaCliente_R, tempoMaxDaRotaVeiculo, cargaMaximaDoVeiculo);	
			System.out.println("Rota Adicionada a Solucao");
			solucao.add(rotaVeiculo);
		}
		ArrayList<Rota> verSolucao = solucao;

		System.out.println("Rotas Inicializadas");
	}

	//TODO Fazer o metodo solucao Inicial
	public void solucaoInicial(){
		System.out.println("Inicio da Solucao Inicial");
		inicializaRotas();
		int qntInseridos = 0, cont = 0, rotaRandomica, nMax=  1000, adidiconarRequisicao, indiceDesembarque;////====>
		//ArrayList<Rota> listaTemp = solucao;
		Integer elementoEmbarque, elementoDesembarque;
		LinkedList<Integer> rota;
		//int[] elementosDaRota;
		//ArrayList<Rota> listaTemp = solucao;
		while(qntInseridos < qntPontos || solucao.size() == 0 || cont == nMax){

			System.out.println("Laco Solucao Inicial"+ cont);

			rotaRandomica = (int) ((Math.random() * qntVeiculos));

			System.out.println("Rota Randomica "+rotaRandomica);

			rota = solucao.get(rotaRandomica).getRota();//Pego uma rota 
			adidiconarRequisicao = data.retornaMenorDistacia(garagemInicial[rotaRandomica],matrizDistancia);

			if(adidiconarRequisicao == 999) break;//Todas as requisicoes foram adicionadas 
			//================================			
			for (int i = 1; i < (rota.size()/2); i++) {
				if(rota.get(i) == (-1)  ){
					//System.out.println("Inserindo no local: "+i+"e no: "+(i+ (rotaTemp.length/2)-1));
					rota.set(i, adidiconarRequisicao);//Embarque
					rota.set(i+ (rota.size()/2) -1, (adidiconarRequisicao - 1 + data.getId().length/2));


					elementoEmbarque = rota.get(i);//Retorna o id
					indiceDesembarque = rota.indexOf(elementoEmbarque + limiteDosEmbarques);//Retorna o id do desembarque
					elementoDesembarque = rota.get(indiceDesembarque);//

					solucao.get(rotaRandomica).adicionaE(i,vetorDosPontos.get(elementoEmbarque).getE());
					solucao.get(rotaRandomica).adicionaL(i,vetorDosPontos.get(elementoEmbarque).getL());
					solucao.get(rotaRandomica).adicionaS(i,vetorDosPontos.get(elementoEmbarque).getS());
					solucao.get(rotaRandomica).adicionAcao(i, vetorDosPontos.get(elementoEmbarque).getAcao());

					break;
				}

			}
			//if (VerificaSeViolaRestricoes()) {//Verifica se viola as restricoes caso nao viole adiciona-se a rota

			//solucao.remove(rotaRandomica);
			solucao.get(rotaRandomica).setRota(rota);//Adiciona o vetor de rotas a solucao de rotas
			data.setRequisicoesVisitadas(adidiconarRequisicao, (adidiconarRequisicao - 1 + data.getId().length/2));
			//}

			//			for (int i = 0; i < rota.size(); i++) {
			//				
			//			}

		}
		ArrayList<Rota> verSolucao = solucao;
		System.out.println("Fim da Soulucao Inicial");
	}

	public void heuristicaDeProgramacao(){
		Rota rotaDaVez;

		float[] variaveisDaVez;
		int elementoInt;
		float elementoFloat;
		Location localtion;
		LinkedList<Float> A, B, D, R, W, T, Q, F, s= new LinkedList<Float>(), e = new LinkedList<Float>(), l = new LinkedList<Float>();
		LinkedList<Integer> elementosDaRota,  acao = new LinkedList<Integer>();
		int tamanhoDaRota, tempoMaxCaronaCliente_R;

		for (int k = 0; k < solucao.size(); k++) {//Para cada rota calcularemos o atraso
			rotaDaVez = solucao.get(k);
			tamanhoDaRota = rotaDaVez.getRota().size(); 
			//Para cada rota faremos
			A =  rotaDaVez.getA();
			B =  rotaDaVez.getB();
			D =  rotaDaVez.getD();
			R =  rotaDaVez.getR();
			W =  rotaDaVez.getW();
			T =  rotaDaVez.getT();				
			Q =  rotaDaVez.getQ();
			F =  rotaDaVez.getF();
			elementosDaRota = rotaDaVez.getRota();
			//e = new float[elementosDaRota.size()];
			//l = new float[elementosDaRota.size()];
			//s = new float[elementosDaRota.size()];
			//acao = new int[elementosDaRota.size()];
			Integer aux = 0;
			for (int i = 0; i < elementosDaRota.size(); i++) {
				aux = elementosDaRota.get(i);//Retorna o id
				e.add(i,vetorDosPontos.get(aux).getE());
				l.add(i,vetorDosPontos.get(aux).getL());
				s.add(i,vetorDosPontos.get(aux).getS());
				acao.add(i, vetorDosPontos.get(aux).getAcao());
			}



			tempoMaxCaronaCliente_R = this.tempMaxCaronaCliente_R;

			//			for (int i = 0; i < tamanhoDaRota; i++) {
			//				localtion = (Location) vetorDosPontos.get(elementosDaRota[i]);
			//				e[i] = localtion.getE();
			//				s[i] = localtion.getS();
			//				acao[i] = localtion.getAcao();
			//			}
			float inicial = 0;
			W.add(0, inicial); 
			A.add(0, inicial); 
			Q.add(0, inicial);//Iniciando as variaveis
			B.add(0, e.get(0));
			D.add(0, B.get(0));

			calculaVariaveis(A, B, D, W, R, Q, e, s, acao, elementosDaRota);			
			calculaFO(F,l,R,B,W, elementosDaRota, tempoMaxCaronaCliente_R);//TODO Falta acabar de implementar

			//Calcular Somatorio de Wp
			float somaWp = 0;
			somaWp = calculaSomatorioWp(somaWp,W);
			B.set(0,  e.get(0) + Math.min(F.get(0), somaWp));
			atualizaVariaveis(A, B, W, D, e, s, elementosDaRota);
			calcularR(B, D, R, elementosDaRota);//Calcular somente os pontos de embarque

			for (int i = 1; i < elementosDaRota.size(); i++) {//Calcular vo != v1 SOMENTE PARA OS PONTOS DE EMBARQUE
				//				B[i+1] = B[i] + s[i] + t[i][i+1] + W[i+1];
				calculaFO(F, l, R, B, W, elementosDaRota, tempoMaxCaronaCliente_R);//TODO IMPLEMENTAR !!
				somaWp = calculaSomatorioWp(somaWp, W);
				if(elementosDaRota.get(i) < limiteDosEmbarques )
					if(elementosDaRota.get(i) != 0){
						//int indiceDesembarque = elementosDaRota.indexOf(limiteDosEmbarques + elementosDaRota.get(i));
						//PEGAR O INDICE DO ELEMENTO APOS O LIMITE DO EMBARQUE DA ROTA
						//R[i] = B[indiceDesembarque ]- D[i];//TODO FAZER UMA VAR GLOBAL P LIMITE PARA P

						B.set(i, B.get(i) + Math.min(F.get(i), somaWp));
						D.set(i, B.get(i) + s.get(i));
						W.set(i, B.get(i) - A.get(i));

						atualizaVariaveis(A, B, W, D, e ,s,elementosDaRota);
						atualizaR(B, D, R, elementosDaRota);
					}
			}

		}//Fim do for para obtermos cada veículo
		ArrayList<Rota> verSolucao = solucao;


	}

	private void atualizaR(LinkedList<Float> b, LinkedList<Float> d, LinkedList<Float> r,	LinkedList<Integer> elementosDaRota2) {
		for (int i = 1; i < elementosDaRota2.size(); i++) {//P e U

			//			if(elementosDaRota2.get(i) < limiteDosEmbarques){
			//				R[i] = B[limiteDosEmbarques + i]- D[i];//TODO FAZER UMA VAR GLOBAL P LIMITE PARA P
			//			}
			if(elementosDaRota2.get(i) < limiteDosEmbarques )
				if(elementosDaRota2.get(i) != 0){
					int indiceDesembarque = elementosDaRota2.indexOf(limiteDosEmbarques + elementosDaRota2.get(i));
					//PEGAR O INDICE DO ELEMENTO APOS O LIMITE DO EMBARQUE DA ROTA
					r.set(i, b.get(indiceDesembarque) - d.get(i));//TODO FAZER UMA VAR GLOBAL P LIMITE PARA P
				}
		}

	}

	private float calculaSomatorioWp(float somaWp, LinkedList<Float> w) {
		for (int z = 1; z < w.size(); z++) {
			somaWp += w.get(z);
		}
		return somaWp;
	}

	private void calcularR(LinkedList<Float> b, LinkedList<Float> d, LinkedList<Float> r, LinkedList<Integer> elementosDaRota2){
		for (int i = 1; i < elementosDaRota2.size(); i++) {//P e U
			if(elementosDaRota2.get(i) < limiteDosEmbarques )
				if(elementosDaRota2.get(i) != 0){
					int indiceDesembarque = elementosDaRota2.indexOf(limiteDosEmbarques + elementosDaRota2.get(i));
					//PEGAR O INDICE DO ELEMENTO APOS O LIMITE DO EMBARQUE DA ROTA
					r.set(i, b.get(indiceDesembarque)- d.get(i));//TODO FAZER UMA VAR GLOBAL P LIMITE PARA P
				}
			//			if(elementosDaRota2.get(i) < limiteDosEmbarques){
			//				R[i] = B[limiteDosEmbarques + i]- D[i];//TODO FAZER UMA VAR GLOBAL P LIMITE PARA P
			//			}
		}
	}

	private void atualizaVariaveis(LinkedList<Float> a, LinkedList<Float> b, LinkedList<Float> w , LinkedList<Float> d, LinkedList<Float> e, LinkedList<Float> s, LinkedList<Integer> elementosDaRota2){
		for (int i = 1; i < elementosDaRota2.size() -1; i++) {//P e U
			a.set(i, d.get(i-1) + t[i-1][i]);//Para P U G+
			b.set(i, Math.max(e.get(i), a.get(i)));//Para P U G+
			if(a.size() != i){
				d.set(i, b.get(i) + s.get(i)); //Para P e U
			}else{
				d.set(i, b.get(i));//Para G+
			}	
			w.set(i, b.get(i) - a.get(i)); // Para P U G+

		}

	}

	private void calculaFO(LinkedList<Float> f, LinkedList<Float> l, LinkedList<Float> r, LinkedList<Float> b, LinkedList<Float> w, LinkedList<Integer> elementosDaRota2, int tempoMaxCaronaCliente_R) {//Calcula o atraso
		int somatorioW = 0;
		float minimoFO, zero = 0;;

		for (int j = 0; j < elementosDaRota2.size(); j++) {
			minimoFO = Integer.MAX_VALUE;
			if(j != 0 && j<=limiteDosEmbarques ){
				for (int p = 0; p < j; p++) {
					somatorioW += w.get(p);
				} 
				if(minimoFO > (somatorioW + Math.min(l.get(j) - b.get(j),  tempoMaxCaronaCliente_R - r.get(j))))//TODO Verificar o R~
					minimoFO = (somatorioW + Math.min(l.get(j) - b.get(j), tempoMaxCaronaCliente_R - r.get(j)));


				f.set(0, Math.min(somatorioW, minimoFO));
			}else
				if(j == 0){ 
					for (int p = 0; p < j; p++) {
						somatorioW += w.get(p);
					} 
					if(minimoFO > (somatorioW + Math.min(l.get(j) - b.get(j), tempoMaxCaronaCliente_R - r.get(j))))//TODO Verificar o R~
						minimoFO = (somatorioW + Math.min(l.get(j) - b.get(j), tempoMaxCaronaCliente_R - r.get(j)));
					f.set(j,  Math.min(somatorioW, minimoFO));
				}else
					f.set(j, zero);
		}
	}

	private void calculaVariaveis(LinkedList<Float> a, LinkedList<Float> b, LinkedList<Float> d, LinkedList<Float> w, LinkedList<Float> r, LinkedList<Float> q, LinkedList<Float> e, LinkedList<Float> s,  LinkedList<Integer> acao, LinkedList<Integer> elementosDaRota2){
		for (int i = 1; i < elementosDaRota2.size(); i++) {//P e U
			a.set(i,  d.get(i-1) + t[i-1][i]);//Para P U G+
			b.set(i,  Math.max(e.get(i), a.get(i)));//Para P U G+
			if(a.size() != i){
				d.set(i,  b.get(i) + s.get(i)); //Para P e U
				q.set(i, q.get(i-1) + acao.get(i));

			}else{
				d.set(i,  b.get(i));//Para G+
				float zero = 0;
				q.set(i, zero);
			}	
			w.set(i, b.get(i) - a.get(i)); // Para P U G+
			if(elementosDaRota2.get(i) < limiteDosEmbarques )
				if(elementosDaRota2.get(i) != 0){
					int indiceDesembarque = elementosDaRota2.indexOf(limiteDosEmbarques + elementosDaRota2.get(i));
					//PEGAR O INDICE DO ELEMENTO APOS O LIMITE DO EMBARQUE DA ROTA
					r.set(i, b.get(indiceDesembarque) - d.get(i));//TODO FAZER UMA VAR GLOBAL P LIMITE PARA P
				}
		}
	}

	//Calcula Funcao Objetivo
	public float calculaFuncaoObjetivo(ArrayList<Rota> solucao){
		float  termoUmUm = 0, termoUmDois = 0, termoUmTres = 0, termoUmQuatro = 0, termoUmCinco = 0, //Os termos estao conforme a funcao
		termoDoisUm = 0 , termoDoisDois = 0, termoDoisTres = 0, 
		termoTresUm = 0, termoTresDois = 0;
		LinkedList<Float> B , D, W, R, T, Q, e, l;
		System.out.println("CALCULA FO ===="+solucao.size());
		for (int k = 0; k < solucao.size(); k++) {
			Rota rota = solucao.get(k);
			elementosDaRota = rota.getRota();
			B = rota.getB();
			D = rota.getD();
			W = rota.getW();
			R = rota.getR();
			T = rota.getT();
			Q = rota.getQ();
			e = rota.getE();
			l = rota.getL();

			//Somatorio das distancias
			for (int i = 0; i < elementosDaRota.size(); i++) {
				termoUmUm += matrizDistancia[elementosDaRota.get(i)][elementosDaRota.get(i)];	
			}

			//Somatorio dos veiculos
			termoUmDois += 1;
			//Somatorio dos tempos de inicio da viagem da garagem inicial menos o tempo de chegada na garagem final
			termoUmTres +=  B.get(elementosDaRota.get(0)) - D.get(elementosDaRota.get((elementosDaRota.size() - 1)));


			for (int i = 1; i < elementosDaRota.size() -1; i++) {//Tiramos as garagens
				if (elementosDaRota.get(i) < limiteDosEmbarques) {//i E P
					//Somatorio do tempo de viagem
					termoUmQuatro += R.get(i);		
				}
				//Somatorio do tempo de espera
				termoUmCinco += W.get(i);//TODO DEU PAU AQUI !!! ===================>
			}
			//==================== Passamos para o segundo termo
			//Calcula o somatorio 
			termoDoisUm += Math.max(0, 
					(B.get(0) - D.get(elementosDaRota.size())) - rota.getTempoMaxDaRotaVeiculo());

			//Calcula o somatorio
			int tempoMaxViagemCliente = rota.getTempoMaxDeViagemPermitidoCliente();

			for (int i = 1; i < elementosDaRota.size() -1; i++) {
				if(elementosDaRota.get(i) < limiteDosEmbarques)
					termoDoisDois += Math.max(0, (R.get(i) - tempoMaxViagemCliente));
			}

			//Calcula o somatorio
			//float[] tempoMaxEsperaNoPonto = rota.getTempoMaximoDeEspera();

			for (int i = 1; i < elementosDaRota.size() -1; i++) {
				if(elementosDaRota.get(i) < limiteDosEmbarques)
					termoDoisTres += Math.max(0, 
							(W.get(i) - W_TempoMaximo_Espera));
			}

			//TODO Calculo do Q E Q~

			//Somatorio 
			for (int i = 0; i < elementosDaRota.size(); i++) {
				termoTresDois += Math.max(0, e.get(i) - B.get(i)) + Math.max(0, B.get(i) - l.get(i)); 
			}

			//			funcaoObjetivo =termoUmUm() + w1*termoUmDois()+termoUmTres()+termoUmQuatro()+termoUmCinco();
			funcaoObjetivo = w0*termoUmUm + w1*termoUmDois + w2*termoUmTres + w3*termoUmQuatro + w4*termoUmCinco + 
			b0*termoDoisUm + b1*termoDoisDois + b2*termoDoisTres + 
			b3*termoTresUm	+ b4*termoTresDois;
		}
		return funcaoObjetivo;
	}//Fim do Calculo da Funcao Objetivo

	//Meta Heuristica ILS-MRD
	public void ILS(int maxIter, int maxIterILS, int kpMax, int delta){

		this.maxIter = maxIter; this.maxIterILS = maxIterILS; 
		this.kpMax = kpMax; this.delta = delta;

		ArrayList<Rota> s_linha = new ArrayList<Rota>(); //Solucao s' conjunto de rotas
		ArrayList<Rota> s_duaslinhas = new ArrayList<Rota>();//Solucao s'' conjunto de rotas
		solucaoInicial();//Cria a solucao inicial 
		heuristicaDeProgramacao();
		ArrayList<Rota> so = solucao;//Atribue a so a solucao inicial
		s_linha = MRD(so, maxIterILS);	

		//solucaoInicial();

		int kp = 0;
		int iter = 0, melhorIter = 0;
		System.out.println("Inicia o primeiro While");
		while (kp < kpMax){
			iter = melhorIter;
			System.out.println("Inicia o Segundo While");
			while(iter < maxIter){
				iter = iter + 1;
				//TODO Perturbqacao
				s_linha = pertubacao(s_linha);
				s_duaslinhas = MRD(so, maxIterILS);//TODO METODO DO MRD
				heuristicaDeProgramacao();
				if (calculaFuncaoObjetivo(s_linha) < calculaFuncaoObjetivo(s_duaslinhas)){
					s_linha = s_duaslinhas;
					melhorIter = iter;
					kp = 0;
				}
			}
			kp = kp + delta;
		}
	}

	private ArrayList<Rota> MRD(ArrayList<Rota> so, int maxIterILS) {
		// TODO Auto-generated method stub
		System.out.println("Esta no MRD");
		int iter = 0;
		while(iter < maxIterILS){
			iter = iter + 1;
			ArrayList<Rota> s_linha = new ArrayList<Rota>(); 
			s_linha = geraAleatoriamente(so);
			if(calculaFuncaoObjetivo(s_linha) < calculaFuncaoObjetivo(so)){
				so = s_linha;//
				iter = 0;
			}
		}
		System.out.println("Saiu do MRD");
		return so;
	}


	private ArrayList<Rota> geraAleatoriamente(ArrayList<Rota> so) {
		int opcaoRandomica = (int) ((Math.random() * 4));
		LinkedList<Integer> rota1, rota2;
		int nRota1Randomica = (int) ((Math.random() * so.size())), nRota2Randomica;
		rota1 = so.get(nRota1Randomica).getRota();//Seleciona uma rota aleatoria
		do {
			nRota2Randomica = (int) ((Math.random() * so.size()));

		} while (nRota1Randomica == nRota2Randomica);//Seleciona outra rota aleatoria
		rota2 = so.get(nRota2Randomica).getRota();
		switch (2) {
		case 0:
			//				rota1 = so.get((int) ((Math.random() * so.size()))).getRota();
			reordenarRota(rota1);
			break;

		case 1:
			//				rota1 = so.get((int) ((Math.random() * so.size()))).getRota();
			//				rota2 = so.get((int) ((Math.random() * so.size()))).getRota();
			realocaRota(rota1, rota2);
			break;

		case 2:

			trocaPontos(so);//rota1, rota2);

			break;

		default:
			realocaBlocosEmbarque(rota1);
			break;
		}

		return so;
	}
	//llll
	private ArrayList<Rota> pertubacao(ArrayList<Rota> sLinha) {
		//TODO Chamar o CPLEX para atuar nas duas piores rotas 

		return null;
	}

	//==========================================================>

	public LinkedList reordenarRota(LinkedList<Integer> rota1){
		int elemento1, elemento2;// = (int) ( 1 + (Math.random() * rota.length));
		LinkedList<Integer> rotaNova = rota1;
		elemento1 = rota1.get(0);
		//TODO FAZER O METODO
		float menorDistancia = Integer.MAX_VALUE, distancia;
		for (int i = 0; i < rota1.size(); i++) {
			rotaNova.add(i, elemento1);
			for (int j = 0; j < rotaNova.size(); j++) {

				distancia = data.getDistancia(elemento1, rota1.get(j));
				if(menorDistancia > distancia)
					menorDistancia = distancia;
				elemento1 = rota1.get(j);
				rota1.add(j, Integer.MAX_VALUE);
			}	 
			//rotaNova[i+1] = elemento1;
		}

		return null;
	}

	public LinkedList realocaRota(LinkedList<Integer> rota1,LinkedList<Integer> rota2 ){
		int elementoRandomica = (int) ( 1 + (Math.random() * rota1.size()));
		int elementoEntra = rota1.get(elementoRandomica);
		int elementoSai = rota1.get(2*elementoRandomica);
		rota1.remove(elementoEntra);
		rota1.remove(elementoSai);

		rota2.add(elementoEntra);
		rota2.add(elementoSai);
		return null;
	}

	public LinkedList trocaPontos(ArrayList<Rota> so){//rota1,LinkedList<Integer> rota2 ){
		int nRota1Randomica = (int) ((Math.random() * so.size())), nRota2Randomica;
		LinkedList<Integer> rota1 = so.get(nRota1Randomica).getRota();//Seleciona uma rota aleatoria
		do {
			nRota2Randomica = (int) ((Math.random() * so.size()));

		} while (nRota1Randomica == nRota2Randomica);//Seleciona outra rota aleatoria
		LinkedList<Integer> rota2 = so.get(nRota2Randomica).getRota();


		int indiceRandomico=(int)(1+ (Math.random() * rota1.size()/2));

		int indiceElemEmbarque = rota1.get(indiceRandomico), indiceDesembarque = 0;
		//int indiceElemDesembarque = rota1.get(elementoRandomica);
		//int elementoEntra = rota1.get(elementoRandomica);
		System.out.println("Limites dos Embarques" + limiteDosEmbarques);
		System.out.println("================================");
		System.out.println("Rota 1" +rota1.toString());
		System.out.println("Rota 2" +rota2.toString());
		Integer elementoEmbarque = 0,elementoDesembarque;
		
		if((rota1.size() == 2)||(rota2.size() == 2)){
			System.out.println("Acabou");
			return null;	
		}
			

		do{
			indiceRandomico= (int)(1+ (Math.random() * rota1.size()/2));
			System.out.println("Indice Randomico " + indiceRandomico);
			elementoEmbarque = rota1.get(indiceRandomico);//Retorna o id
			System.out.println("592 Elemento de Embarque  "+ elementoEmbarque );
			
		}while(elementoEmbarque > limiteDosEmbarques);
		System.out.println("Limites dos Embarques" + limiteDosEmbarques);
		indiceDesembarque = rota1.indexOf(elementoEmbarque + limiteDosEmbarques);//Retorna o id do desembarque
		System.out.println("592 Elemento de Desembarque  "+ (elementoEmbarque + limiteDosEmbarques));
		elementoDesembarque = rota1.get(indiceDesembarque);//

		//int indiceSai = rota1.indexOf(elementoRandomica);

		rota1.remove(elementoEmbarque);//remove(elementoEntra);
		rota1.remove(elementoDesembarque);
		//Selecionando as variaveis de cada elemento da rota modificado
		float elemento_embarque_E = so.get(nRota1Randomica).getE().get(indiceRandomico);
		float elemento_embarque__L = so.get(nRota1Randomica).getL().get(indiceRandomico);
		float elemento_embarque__S = so.get(nRota1Randomica).getS().get(indiceRandomico);
		int elemento_embarque__Acao = so.get(nRota1Randomica).getAcao().get(indiceRandomico);

		float elemento_desembarque_E = so.get(nRota1Randomica).getE().get(indiceDesembarque);
		float elemento_desembarque__L = so.get(nRota1Randomica).getL().get(indiceDesembarque);
		float elemento_desembarque__S = so.get(nRota1Randomica).getS().get(indiceDesembarque);
		float elemento_desembarque__Acao = so.get(nRota1Randomica).getAcao().get(indiceDesembarque);
		//Removendo "e, l , s ,acao" do embarque
//		so.get(nRota1Randomica).removetE(indiceRandomico);
//		so.get(nRota1Randomica).removetL(indiceRandomico);
//		so.get(nRota1Randomica).removetS(indiceRandomico);
//		so.get(nRota1Randomica).removetAcao(indiceRandomico);

		so.get(nRota1Randomica).removetE(indiceRandomico);
		so.get(nRota1Randomica).removetL(indiceRandomico);
		so.get(nRota1Randomica).removetS(indiceRandomico);
		so.get(nRota1Randomica).removetAcao(indiceRandomico);
		so.get(nRota1Randomica).removetA(indiceRandomico);
		so.get(nRota1Randomica).removetB(indiceRandomico);
		so.get(nRota1Randomica).removetD(indiceRandomico);
		so.get(nRota1Randomica).removetR(indiceRandomico);
		so.get(nRota1Randomica).removetW(indiceRandomico);
		so.get(nRota1Randomica).removetQ(indiceRandomico);
		so.get(nRota1Randomica).removetT(indiceRandomico);

		//Removendo "e, l , s ,acao" do desembarque
		so.get(nRota1Randomica).removetE(indiceDesembarque);
		so.get(nRota1Randomica).removetL(indiceDesembarque);
		so.get(nRota1Randomica).removetS(indiceDesembarque);
		so.get(nRota1Randomica).removetAcao(indiceDesembarque);
		so.get(nRota1Randomica).removetA(indiceDesembarque);
		so.get(nRota1Randomica).removetB(indiceDesembarque);
		so.get(nRota1Randomica).removetD(indiceDesembarque);
		so.get(nRota1Randomica).removetR(indiceDesembarque);
		so.get(nRota1Randomica).removetW(indiceDesembarque);
		so.get(nRota1Randomica).removetQ(indiceDesembarque);
		so.get(nRota1Randomica).removetT(indiceDesembarque);
		//rota1.remove(elementoDesembarque);
		int count = 0,elementoIndiceDesembarque, elementoIndiceEmbarque = (int)( 1 + (Math.random() * rota1.size()));

		do{
			if(count > 10)
				elementoIndiceEmbarque = (int)( 1 + (Math.random() * rota1.size()));
			count++;
			elementoIndiceDesembarque = (int)( 1 + (Math.random() * rota2.size()));
		}while(elementoIndiceEmbarque > elementoIndiceDesembarque );
		//Adicona na rota2 os valores das variaveis de embarque
		rota2.add(elementoIndiceEmbarque,elementoEmbarque);		
		so.get(nRota2Randomica).adicionaE(elementoIndiceEmbarque, elemento_embarque_E);
		so.get(nRota2Randomica).adicionaL(elementoIndiceEmbarque, elemento_embarque__L);
		so.get(nRota2Randomica).adicionaS(elementoIndiceEmbarque, elemento_embarque__S);
		so.get(nRota2Randomica).adicionaAcao(elementoIndiceEmbarque, elemento_embarque__Acao);
		so.get(nRota2Randomica).adicionaE(elementoIndiceEmbarque, elemento_embarque_E);
		so.get(nRota2Randomica).adicionaL(elementoIndiceEmbarque, elemento_embarque__L);
		so.get(nRota2Randomica).adicionaS(elementoIndiceEmbarque, elemento_embarque__S);
		so.get(nRota2Randomica).adicionaE(elementoIndiceEmbarque, elemento_embarque__Acao);
		so.get(nRota2Randomica).adicionaA(elementoIndiceEmbarque, 0);
		so.get(nRota2Randomica).adicionaB(elementoIndiceEmbarque, 0);
		so.get(nRota2Randomica).adicionaD(elementoIndiceEmbarque, 0);
		so.get(nRota2Randomica).adicionaR(elementoIndiceEmbarque, 0);
		so.get(nRota2Randomica).adicionaW(elementoIndiceEmbarque, 0);
		so.get(nRota2Randomica).adicionaQ(elementoIndiceEmbarque, 0);
		so.get(nRota2Randomica).adicionaT(elementoIndiceEmbarque, 0);
		//Adicona na rota2 os valores das variaveis de desembarque		
		rota2.add(elementoIndiceDesembarque, elementoDesembarque);
		so.get(nRota2Randomica).adicionaE(elementoIndiceDesembarque, elemento_embarque_E);
		so.get(nRota2Randomica).adicionaL(elementoIndiceDesembarque, elemento_embarque__L);
		so.get(nRota2Randomica).adicionaS(elementoIndiceDesembarque, elemento_embarque__S);
		so.get(nRota2Randomica).adicionaE(elementoIndiceDesembarque, elemento_embarque__Acao);
		so.get(nRota2Randomica).adicionaA(elementoIndiceDesembarque, 0);
		so.get(nRota2Randomica).adicionaB(elementoIndiceDesembarque, 0);
		so.get(nRota2Randomica).adicionaD(elementoIndiceDesembarque, 0);
		so.get(nRota2Randomica).adicionaR(elementoIndiceDesembarque, 0);
		so.get(nRota2Randomica).adicionaW(elementoIndiceDesembarque, 0);
		so.get(nRota2Randomica).adicionaQ(elementoIndiceDesembarque, 0);
		so.get(nRota2Randomica).adicionaT(elementoIndiceDesembarque, 0);

		so.get(nRota1Randomica).setRota(rota1);
		so.get(nRota2Randomica).setRota(rota2);

		return null;

	}

	public void realocaBlocosEmbarque(LinkedList<Integer> rota1){
		LinkedList aInverter = null;
		Integer elemento = 0;
		int count = 0, idDesembarque = (data.quantidadeVeiculos + 1);
		elemento = (Integer) rota1.get(count);

		do{
			aInverter.addFirst(elemento);
			rota1.remove(count);
			count++;
			elemento = (Integer) rota1.get(count);
		}
		while(elemento < idDesembarque);

		do{
			rota1.addFirst(aInverter.get(count));
		}while(count-->0);
	}

	//public LinkedList getVizinho() {
	//	try {
	//		Rota s = (Solution) clone();
	//		int op = (Math.random() < 0.5) ? 0 : 1;
	//		switch (op) {
	//			case 0 :
	//				s.intra();
	//				break;
	//			case 1 :
	//				s.inter();
	//				break;
	//		}
	//		return s;
	//	} catch (CloneNotSupportedException cnse) {
	//		cnse.printStackTrace();
	//	}
	//	return null;
	//}

}//Fim da classe DARP



